package com.atwulidun.idivideandconquer02;
// 问题描述：
// 设有n=2^k个运动员要进行网球循环赛，现要设计一个满足以下要求的比赛日程表：
// (1)每个选手必须与其他n-1个选手各赛一次；
// (2)每个选手一天只能参赛一次；
// (3)循环赛在n-1天内结束。
// 按此要求将比赛日程表设计成有n行和n-1列的一个表。
// 在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手。
// 思路分析：
// 按分治策略，我们可以将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。
// 递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，只要让这两个选手进行比赛就可以了。
// 将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角
// 步骤：
// 1.先用for循环输出日程表的第一行

// 2.对第二行进行填充，操作4次
// 1 2|3 4|5 6|7 8
// --- --- --- ---
// 2 1|4 3|6 5|8 7

// 3.对第三、四行进行填充，操作2次
// 1 2 3 4|5 6 7 8
// 2 1 4 3|6 5 8 7
// ------- -------
// 3 4 1 2|7 8 5 6
// 4 3 2 1|8 7 6 5

// 4.对五、六、七、八行进行填充，操作1次
// 1 2 3 4|5 6 7 8
// 2 1 4 3|6 5 8 7
// 3 4 1 2|7 8 5 6
// 4 3 2 1|8 7 6 5
// ------- -------
// 5 6 7 8|1 2 3 4
// 6 5 8 7|2 1 4 3
// 7 8 5 6|3 4 1 2
// 8 7 6 5|4 3 2 1

public class RoundRobinSchedule {
    public static void main(String[] args) {
        int[][] arr = roundRobinSchedule(3);
        for (int[] ints : arr) {
            for (int anInt : ints) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }
    }

    public static int[][] roundRobinSchedule(int k) {
        // 建立维度为2的k次方的二维数组
        int n = 1 << k;
        int[][] arr = new int[n][n];
        // 首先输出日程表的第一行
        for (int i = 0; i < n; i++) {
            arr[0][i] = i + 1;
        }
        // 对日程表进行填充
        // 外层循环控制填充的轮数，跟k的数值一样，同时i还标记每一轮从第几行开始填充(1,2,4,...)
        // 注意：每一轮都是把第一行的元素复制到第i行，只是复制的矩阵的维度有所变化(4次1*1,2次2*2,1次4*4,...)
        for (int i = 1; i < n; i <<= 1) {
            // 内层循环控制每轮进行交叉填充的次数(第一轮为2的k-1次方，第二轮为2的k-2次方，...，直到2的0次方也就是一次)，
            // 同时还标记每次填充是从第几列开始
            for (int j = 0; j < n; j += 2 * i) {
                // 1 2|3 4|5 6|7 8
                // --- --- --- ---
                // 2 1|4 3|6 5|8 7
                // 拿第一轮第一次为例:
                // 左上角1坐标：(0,j)
                // 右下角1坐标：(i,j+i)
                // 右上角2坐标：(0,j+i)
                // 左下角2坐标：(i,j)
                // 把左上角的矩阵复制到右下角
                copy(arr, 0, j, i, j + i, i);
                // 把右上角的矩阵复制到左下角
                copy(arr, 0, j + i, i, j, i);
            }
        }
        return arr;
    }

    // 以下为填充的方法
    // 表示把以arr[rowFrom][colFrom]为左上角的维度为r*r的二维矩阵复制到以arr[rowTo][colTo]为左上角的矩阵中去
    private static void copy(int[][] arr, int rowFrom, int colFrom, int rowTo, int colTo, int r) {
        // 外层循环控制行
        for (int i = 0; i < r; i++) {
            // 内层循环控制列
            for (int j = 0; j < r; j++) {
                arr[rowTo + i][colTo + j] = arr[rowFrom + i][colFrom + j];
            }
        }
    }
}
